SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Path graph</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Path graph</span></span>

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">This article is about a family of graphs. For paths as parts of arbitrary graphs, see <a href="Path_(graph_theory)" title="Path (graph theory)">Path (graph theory)</a>.</div>

<div role="note" class="hatnote navigation-not-searchable">Not to be confused with <a href="Line_graph" title="Line graph">line graph</a>.</div>

/* start https://en.wikipedia.org/ */

@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-image img{background-color:var(--background-color-inverted,#f8f9fa)}html.skin-theme-clientpref-night .mw-parser-output .infobox-image img[src$="svg.png"]{filter:invert(1);background-color:transparent}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-image img{background-color:var(--background-color-inverted,#f8f9fa)}html.skin-theme-clientpref-os .mw-parser-output .infobox-image img[src$="svg.png"]{filter:invert(1);background-color:transparent}}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1295905060">

/* start https://en.wikipedia.org/ */

.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}

/* end https://en.wikipedia.org/ */

</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Path graph</th></tr><tr><td colspan="2" class="infobox-image"><span typeof="mw:File"></span><div class="infobox-caption">A path graph on 6 vertices</div></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Vertex_(graph_theory)" title="Vertex (graph theory)">Vertices</a></th><td class="infobox-data"><span class="texhtml mvar" style="font-style:italic;">n</span></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">Edges</a></th><td class="infobox-data"><span class="texhtml"><i>n</i> − 1</span></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Distance_(graph_theory)" title="Distance (graph theory)">Radius</a></th><td class="infobox-data"><span class="texhtml">⌊<i>n</i>/2⌋</span></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Diameter_(graph_theory)" title="Diameter (graph theory)">Diameter</a></th><td class="infobox-data"><span class="texhtml"><i>n</i> − 1</span></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Graph_automorphism" title="Graph automorphism">Automorphisms</a></th><td class="infobox-data">2</td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Chromatic_number" class="mw-redirect" title="Chromatic number">Chromatic number</a></th><td class="infobox-data">2</td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Chromatic_index" class="mw-redirect" title="Chromatic index">Chromatic index</a></th><td class="infobox-data">2</td></tr><tr><th scope="row" class="infobox-label" style="width:50%;"><a href="Spectral_graph_theory" title="Spectral graph theory">Spectrum</a></th><td class="infobox-data"><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{2\cos \left({\frac {k\pi }{n+1}}\right);}">

<mrow>

<mfrac>

<mrow>

</mrow>

<mrow>

</mrow>

</mfrac>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{2\cos \left({\frac {k\pi }{n+1}}\right);}</annotation>

</semantics>

</math></span><img src="./b3a77d9a74b2be1e1479b4fc70bac7eaf4fbe7a3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:16.125ex; height:6.176ex;" alt="{\displaystyle \{2\cos \left({\frac {k\pi }{n+1}}\right);}" loading="lazy"></span><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k=1,\ldots ,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle k=1,\ldots ,n\}}</annotation>

</semantics>

</math></span><img src="./6ff1e2f11e78ee2458a0e5d27455f340d4badac4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.208ex; height:2.843ex;" alt="{\displaystyle k=1,\ldots ,n\}}" loading="lazy"></span></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;">Properties</th><td class="infobox-data"><a href="Unit_distance_graph" title="Unit distance graph">Unit distance</a><br><a href="Bipartite_graph" title="Bipartite graph">Bipartite graph</a><br><a href="Tree_(graph_theory)" title="Tree (graph theory)">Tree</a></td></tr><tr><th scope="row" class="infobox-label" style="width:50%;">Notation</th><td class="infobox-data"><span class="texhtml mvar" style="font-style:italic;">P<sub>n</sub></span><sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup></td></tr><tr><td colspan="2" class="infobox-below"><a href="List_of_graphs_by_edges_and_vertices" title="List of graphs by edges and vertices">Table of graphs and parameters</a></td></tr></tbody></table>

<p>In the <a href="Mathematics" title="Mathematics">mathematical</a> field of <a href="Graph_theory" title="Graph theory">graph theory</a>, a <b>path graph</b> (or <b>linear graph</b>) is a <a href="Graph_(discrete_mathematics)" title="Graph (discrete mathematics)">graph</a> whose <a href="Vertex_(graph_theory)" title="Vertex (graph theory)">vertices</a> can be listed in the order <span class="texhtml"><i>v</i><sub>1</sub>, <i>v</i><sub>2</sub>, ..., <i>v<sub>n</sub></i></span> such that the <a href="Edge_(graph_theory)" class="mw-redirect" title="Edge (graph theory)">edges</a> are <span class="texhtml">{<i>v<sub>i</sub></i>, <i>v</i><sub><i>i</i>+1</sub></span>} where <span class="texhtml"><i>i</i> = 1, 2, ..., <i>n</i> − 1</span>. Equivalently, a path with at least two vertices is <a href="Connectivity_(graph_theory)" title="Connectivity (graph theory)">connected</a> and has two terminal vertices (vertices of <a href="Degree_(graph_theory)" title="Degree (graph theory)">degree</a> 1), while all others (if any) have degree 2.

</p><p>Paths are often important in their role as <a href="Glossary_of_graph_theory#Subgraphs" title="Glossary of graph theory">subgraphs</a> of other graphs, in which case they are called <a href="Path_(graph_theory)" title="Path (graph theory)">paths</a> in that graph. A path is a particularly simple example of a <a href="Tree_(graph_theory)" title="Tree (graph theory)">tree</a>, and in fact the paths are exactly the trees in which no vertex has degree 3 or more. A <a href="Disjoint_union_of_graphs" title="Disjoint union of graphs">disjoint union</a> of paths is called a <a href="Linear_forest" title="Linear forest">linear forest</a>.

</p><p>Paths are fundamental concepts of graph theory, described in the introductory sections of most graph theory texts. See, for example, Bondy and Murty (1976), Gibbons (1985), or Diestel (2005).

</p>

<div class="mw-heading mw-heading2"><h2 id="As_Dynkin_diagrams">As Dynkin diagrams</h2></div>

<p>In <a href="Algebra" title="Algebra">algebra</a>, path graphs appear as the <a href="Dynkin_diagram" title="Dynkin diagram">Dynkin diagrams</a> of type A. As such, they classify the <a href="Root_system" title="Root system">root system</a> of type A and the <a href="Weyl_group" title="Weyl group">Weyl group</a> of type A, which is the <a href="Symmetric_group" title="Symmetric group">symmetric group</a>.

</p>

<ul><li><a href="Path_(graph_theory)" title="Path (graph theory)">Path (graph theory)</a></li>

<li><a href="Ladder_graph" title="Ladder graph">Ladder graph</a></li>

<li><a href="Caterpillar_tree" title="Caterpillar tree">Caterpillar tree</a></li>

<li><a href="Complete_graph" title="Complete graph">Complete graph</a></li>

<li><a href="Null_graph" title="Null graph">Null graph</a></li>

<li><a href="Path_decomposition" class="mw-redirect" title="Path decomposition">Path decomposition</a></li>

<li><a href="Cycle_(graph_theory)" title="Cycle (graph theory)">Cycle (graph theory)</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">While it is most common to use <span class="texhtml mvar" style="font-style:italic;">P<sub>n</sub></span> for a path of <span class="texhtml mvar" style="font-style:italic;">n</span> vertices, some authors (e.g. Diestel) use <span class="texhtml mvar" style="font-style:italic;">P<sub>n</sub></span> for a path of <span class="texhtml mvar" style="font-style:italic;">n</span> <i>edges</i> and <span class="texhtml"><i>n</i>+1</span> vertices.</span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBondy,_J._A.Murty,_U._S._R.1976" class="citation book cs1"><a href="John_Adrian_Bondy" title="John Adrian Bondy">Bondy, J. A.</a>; <a href="U._S._R._Murty" title="U. S. R. Murty">Murty, U. S. R.</a> (1976). <a rel="nofollow" class="external text" href="https://archive.org/details/graphtheorywitha0000bond/page/12"><i>Graph Theory with Applications</i></a>. North Holland. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/graphtheorywitha0000bond/page/12">12–21</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-444-19451-7</bdi>.</cite></li>

<li><cite id="CITEREFDiestel,_Reinhard2005" class="citation book cs1"><a href="Reinhard_Diestel" title="Reinhard Diestel">Diestel, Reinhard</a> (2005). <a rel="nofollow" class="external text" href="http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/"><i>Graph Theory</i></a> (3rd ed.). <a href="Graduate_Texts_in_Mathematics" title="Graduate Texts in Mathematics">Graduate Texts in Mathematics</a>, vol. 173, Springer-Verlag. pp. <span class="nowrap">6–</span>9. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>3-540-26182-6</bdi>.</cite></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><span class="citation mathworld" id="Reference-Mathworld-Path_Graph"><cite id="CITEREFWeisstein" class="citation web cs1"><a href="Eric_W._Weisstein" title="Eric W. Weisstein">Weisstein, Eric W.</a> <a rel="nofollow" class="external text" href="https://mathworld.wolfram.com/PathGraph.html">"Path Graph"</a>. <i><a href="MathWorld" title="MathWorld">MathWorld</a></i>.</cite></span></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-11-15" href="https://en.wikipedia.org/wiki/?title=Path_graph&oldid=1257497724">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>